UVa/10054 - The Necklace/10054.cpp

   1 /*
   2   Problem: 10054 - The Necklace
   3   Andrés Mejía-Posada (andmej@gmail.com)
   4 */
   5 using namespace std;
   6 #include <algorithm>
   7 #include <iostream>
   8 #include <iterator>
   9 #include <sstream>
  10 #include <fstream>
  11 #include <cassert>
  12 #include <climits>
  13 #include <cstdlib>
  14 #include <cstring>
  15 #include <string>
  16 #include <cstdio>
  17 #include <vector>
  18 #include <cmath>
  19 #include <queue>
  20 #include <deque>
  21 #include <stack>
  22 #include <list>
  23 #include <map>
  24 #include <set>
  25
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 const int MAXN = 51;
  29
  30 bool visited[MAXN];
  31 int adj[MAXN][MAXN], degree[MAXN];
  32 int n;
  33 deque<int> path;
  34
  35 void visit_component(int u){
  36   if (visited[u]) return;
  37   visited[u] = true;
  38   for (int v=0; v<n; ++v){
  39     if (adj[u][v]) visit_component(v);
  40   }
  41 }
  42
  43 void find_euler_path(int u){
  44   for (int v=0; v<n; ++v){
  45     if (adj[u][v]){
  46       adj[u][v]--, adj[v][u]--;
  47       find_euler_path(v);
  48     }
  49   }
  50   path.push_front(u);
  51 }
  52
  53 int main(){
  54   int T;
  55   scanf("%d", &T);
  56   for (int t=1; t<=T; ++t){
  57     if (t > 1) printf("\n");
  58     printf("Case #%d\n", t);
  59
  60     bzero(visited, sizeof visited);
  61     bzero(adj, sizeof adj);
  62     bzero(degree, sizeof degree);
  63     path.clear();
  64     n = 0;
  65
  66     int edges;
  67     for(scanf("%d", &edges); edges--; ){
  68       int u, v;
  69       scanf("%d %d", &u, &v);
  70       n = max(n, u+1);
  71       n = max(n, v+1);
  72       degree[u]++, degree[v]++;
  73       adj[u][v]++, adj[v][u]++;
  74     }
  75
  76     for (int i=0; i<n; ++i){
  77       if (degree[i] > 0){
  78         visit_component(i);
  79         break;
  80       }
  81     }
  82
  83     bool impossible = false;
  84     for (int i=0; i<n; ++i){
  85       if (degree[i] > 0 && !visited[i] || degree[i] % 2 == 1){
  86         impossible = true;
  87         break;
  88       }
  89     }
  90
  91     if (!impossible){
  92       for (int i=0; i<n; ++i){
  93         if (degree[i] > 0){
  94           find_euler_path(i);
  95           break;
  96         }
  97       }
  98     }
  99
 100     if (impossible){
 101       printf("some beads may be lost\n");
 102     }else{
 103       for (int i=0; i<path.size()-1; ++i){
 104         printf("%d %d\n", path[i], path[i+1]);
 105       }
 106     }
 107   }
 108   return 0;
 109 }